lib/Mi manual de algoritmos/version_world_finals_2009/src/grafos/tarjan.cpp

   1 /* Complexity: O(E + V)
   2  Tarjan's algorithm for finding strongly connected
   3 components.
   4
   5  *d[i] = Discovery time of node i. (Initialize to -1)
   6  *low[i] = Lowest discovery time reachable from node
   7  i. (Doesn't need to be initialized)
   8  *scc[i] = Strongly connected component of node i. (Doesn't
   9  need to be initialized)
  10  *s = Stack used by the algorithm (Initialize to an empty
  11  stack)
  12  *stacked[i] = True if i was pushed into s. (Initialize to
  13  false)
  14  *ticks = Clock used for discovery times (Initialize to 0)
  15  *current_scc = ID of the current_scc being discovered
  16  (Initialize to 0)
  17 */
  18 vector<int> g[MAXN];
  19 int d[MAXN], low[MAXN], scc[MAXN];
  20 bool stacked[MAXN];
  21 stack<int> s;
  22 int ticks, current_scc;
  23 void tarjan(int u){
  24   d[u] = low[u] = ticks++;
  25   s.push(u);
  26   stacked[u] = true;
  27   const vector<int> &out = g[u];
  28   for (int k=0, m=out.size(); k<m; ++k){
  29     const int &v = out[k];
  30     if (d[v] == -1){
  31       tarjan(v);
  32       low[u] = min(low[u], low[v]);
  33     }else if (stacked[v]){
  34       low[u] = min(low[u], low[v]);
  35     }
  36   }
  37   if (d[u] == low[u]){
  38     int v;
  39     do{
  40       v = s.top();
  41       s.pop();
  42       stacked[v] = false;
  43       scc[v] = current_scc;
  44     }while (u != v);
  45     current_scc++;
  46   }
  47 }